public class Solution1049 {
    public int getRes(int num,int sum){
       return Math.abs(sum-num*2);
    }

    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for (int tmpNum:stones) {
            sum+=tmpNum;
        }
        int[][] dp=new int[stones.length][sum+1];
        dp[0][stones[0]]=1;
        for (int i = 1; i < stones.length; i++) {
            int tmpNum=stones[i];
            int[] last=dp[i-1];
            int[] tmp=dp[i];
            for (int j = 0; j < last.length; j++) {
                int lastNum=last[j];
                if(lastNum==1){
                    tmp[j]=lastNum;
                    tmp[j+tmpNum]=lastNum;
                }
            }
            tmp[tmpNum]=1;
        }
        int[] last=dp[stones.length-1];
        int min=Integer.MAX_VALUE;
        for (int i = 0; i < last.length; i++) {
            if(last[i]==1){
                min=Math.min(min,getRes(i,sum));
            }
        }
        return min;
    }

    public static void main(String[] args) {
        Solution1049 s=new Solution1049();
        System.out.println(s.lastStoneWeightII(new int[]{2,7,4,1,8,1}));
    }
}
